#include "hdf_tree.h"
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//多叉树的根节点，初始状态为不存在
static DeviceResourceNode *g_rootNode = NULL;

//遍历根节点为curNode的多叉树，针对每个节点执行func指定函数，并给func函数传递args参数
// 也支持遍历过程中删除节点
//递归版本，先根后叶
static void TraverseTree(DeviceResourceNode *curNode, bool (*func)(DeviceResourceNode*, void *args),void *args)
{
	bool stop = false;
	if(curNode == NULL)
		return ;
	
  DeviceResourceNode *child, *next;
	child = curNode->child;
	stop = func(curNode, args);
	if (stop)
		return;

	while(child != NULL)
	{
		next = child->sibling;
		TraverseTree(child, func,args);
		child = next;
	}

}

//同上
//循环版本，先根后叶
static void TraverseTree2(DeviceResourceNode *curNode, bool (*func)(DeviceResourceNode*, void *args),void *args)
{
	bool stop = false;	
  while (curNode != NULL) 
	{ 
		struct DeviceResourceNode *nextNode = curNode;
		stop = func(curNode, args);
		if (stop)
			return;
		if(curNode->child != NULL)   
		{
			nextNode = curNode->child;
		}     
		else
		{			
		  while (nextNode->parent && !nextNode->sibling) 
			{
         		nextNode = nextNode->parent;
      }
 		  nextNode = nextNode->sibling;         	
		}
		curNode = nextNode;
  }
    
}

//先叶后跟遍历(循环)，课后作业
//先叶后跟遍历(递归), 课后作业
bool DeleteNode(DeviceResourceNode *node, void *args)
{
	free(node);
	//需要继续遍历，辅助删除整颗树
	return false;
}

//删除整颗多叉树
void DeleteTree()
{
	TraverseTree(g_rootNode, DeleteNode,NULL);
	//TraverseTree2(g_rootNode, DeleteNode,NULL);
	g_rootNode = NULL;
}

//显示某具体节点的具体信息以及其父兄关系
bool ShowNode(DeviceResourceNode *node, void *args)
{
	printf("%s\t", node->name);
	if(node->parent) printf("parent: %s\t", node->parent->name);
	if(node->sibling) printf("sibling: %s\t", node->sibling->name);
	if(node->child) printf("child %s", node->child->name);
	printf("\n");
	return false;
}

//显示整颗树的信息，常规遍历，未进行优化处理
void ShowTree()
{	
	TraverseTree(g_rootNode, ShowNode, NULL);
	//TraverseTree2(g_rootNode, DeleteNode,NULL);
}

//特殊的递归函数，支持节点所在层数信息，用于支持更优化的多叉树信息显示
void ShowNode2(DeviceResourceNode *node)
{
	static int depth = 0;

	if(node == NULL)
		return;
	for(int i=0; i<depth; i++)
		printf("  ");
	printf("%s\n", node->name);
	DeviceResourceNode *child, *next;	
	child = node->child;
	depth++;
	for(next = child; next != NULL; next = next->sibling)
	{		
		ShowNode2(next);		
	}
	depth--;
}

//优化后的多叉树信息显示
void ShowTree2()
{
	ShowNode2(g_rootNode);
}

struct SearchNodeParams
{
	char nodeNames[NAMESIZE];  //查找此名称对应的节点
	DeviceResourceNode *retNode;  //记录查找后的结果
};

//判断节点名称是否匹配
bool MatchNodeByName(DeviceResourceNode *node, void *args)
{
	struct SearchNodeParams *params = (struct SearchNodeParams *)args;	
	
	if(strcmp(node->name, params->nodeNames) == 0)
	{
		params->retNode = node;
		return true;
	}

	return false;
}

//按名称在多叉树种查询指定名称的节点，并返回
DeviceResourceNode *SearchNode(char *name)
{
	struct SearchNodeParams params;
	params.retNode = NULL;
	strncpy(params.nodeNames, name, NAMESIZE);
	TraverseTree(g_rootNode, MatchNodeByName, &params);
	//TraverseTree2(g_rootNode, MatchNodeByName, &params);
	return params.retNode;
}

//将名称为child的节点添加到名称为parent的节点上：   child为新节点，parent为已经存在的节点
//例外情况，child, parent都不存在，如果此时树为空，则根据child的值添加树根节点
void AddNode(char *parent, char*child)
{
	DeviceResourceNode *parentNode, *childNode;
	parentNode = SearchNode(parent);
	childNode = SearchNode(child);
	if(parentNode == NULL && childNode == NULL && g_rootNode == NULL)
	{
		g_rootNode = (DeviceResourceNode*)malloc(sizeof(DeviceResourceNode));
		strncpy(g_rootNode->name, child, NAMESIZE);
		return ;	
	}

	if(parentNode == NULL
	|| childNode != NULL)
	{
		printf("-----------------------------------------------\n");
		printf("Cann't add child %s to parent %s\n", child, parent);
		printf("-----------------------------------------------\n");
		printf("Now the tree is \n");
		printf("-----------------------------------------------\n");
		ShowTree2();
		return ;
	}
	

	childNode = (DeviceResourceNode*)malloc(sizeof(DeviceResourceNode));
	strncpy(childNode->name, child, NAMESIZE);
	childNode->sibling = parentNode->child;
	childNode->child = NULL;
	childNode->parent = parentNode;
	parentNode->child = childNode;
}





